{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #回文链表"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #recursion #linked-list #two-pointers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #递归 #链表 #双指针"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: isPalindrome"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #回文链表"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个链表的 <strong>头节点&nbsp;</strong><code>head</code><strong>&nbsp;，</strong>请判断其是否为回文链表。</p>\n",
    "\n",
    "<p>如果一个链表是回文，那么链表节点序列从前往后看和从后往前看是相同的。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><strong><img alt=\"\" src=\"https://pic.leetcode-cn.com/1626421737-LjXceN-image.png\" /></strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> head = [1,2,3,3,2,1]\n",
    "<strong>输出:</strong> true</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><strong><img alt=\"\" src=\"https://pic.leetcode-cn.com/1626422231-wgvnWh-image.png\" style=\"width: 138px; height: 62px;\" /></strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> head = [1,2]\n",
    "<strong>输出:</strong> false\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>链表 L 的长度范围为 <code>[1, 10<sup><span style=\"font-size: 9.449999809265137px;\">5</span></sup>]</code></li>\n",
    "\t<li><code>0&nbsp;&lt;= node.val &lt;= 9</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>进阶：</strong>能否用&nbsp;O(n) 时间复杂度和 O(1) 空间复杂度解决此题？</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><meta charset=\"UTF-8\" />注意：本题与主站 234&nbsp;题相同：<a href=\"https://leetcode-cn.com/problems/palindrome-linked-list/\">https://leetcode-cn.com/problems/palindrome-linked-list/</a></p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [aMhZSa](https://leetcode.cn/problems/aMhZSa/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [aMhZSa](https://leetcode.cn/problems/aMhZSa/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,2,1]', '[1,2]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        if not head.next:\n",
    "            return True\n",
    "        left = None\n",
    "        slow = head\n",
    "        fast = head\n",
    "        even = True\n",
    "        while fast and fast.next:\n",
    "            fast = fast.next.next\n",
    "            if fast == None:\n",
    "                even = False\n",
    "            #print(fast.val, fast.next.val)\n",
    "            next_node = slow.next\n",
    "            slow.next = left\n",
    "            left = slow\n",
    "            slow = next_node\n",
    "        if even:\n",
    "            slow = slow.next\n",
    "        while left.val == slow.val:\n",
    "            left = left.next\n",
    "            slow = slow.next\n",
    "            if left == None and slow == None:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        if head == None or head.next == None:\n",
    "            return True \n",
    "        pFast = head.next\n",
    "        pSlow = head\n",
    "        while pFast:\n",
    "            pSlow = pSlow.next\n",
    "            if pFast.next and pFast.next.next:\n",
    "                pFast = pFast.next.next\n",
    "            else:\n",
    "                break\n",
    "        temp = pSlow\n",
    "        end = None\n",
    "        while (temp) :\n",
    "            newTemp = temp.next\n",
    "            temp.next = end\n",
    "            if newTemp == None:\n",
    "                break\n",
    "            end = temp\n",
    "            temp = newTemp\n",
    "        p1 = head\n",
    "        p2 = temp\n",
    "        while p1 and p2:\n",
    "            if p1.val != p2.val: \n",
    "                return False\n",
    "            p1 = p1.next\n",
    "            p2 = p2.next\n",
    "        return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        if not (head and head.next):\n",
    "            return True\n",
    "\n",
    "        count = 1\n",
    "        fast, slow = head, head\n",
    "        while fast and fast.next:\n",
    "            fast, slow = fast.next.next, slow.next\n",
    "\n",
    "            if  fast:\n",
    "                count += 2\n",
    "            else:\n",
    "                count += 1\n",
    "\n",
    "        if count % 2 == 1:\n",
    "            slow = slow.next\n",
    "        \n",
    "        slow = self.reverse(slow)\n",
    "\n",
    "        while slow:\n",
    "            if slow.val != head.val:\n",
    "                return False\n",
    "            slow = slow.next\n",
    "            head = head.next\n",
    "        \n",
    "        return True\n",
    "        \n",
    "    \n",
    "    def reverse(self, head: ListNode) -> ListNode:\n",
    "        if not (head and head.next):\n",
    "            return head\n",
    "\n",
    "        result = head\n",
    "        head = head.next\n",
    "        result.next = None\n",
    "\n",
    "        while head:\n",
    "            temp = head\n",
    "            head = head.next\n",
    "            temp.next = result\n",
    "            result = temp\n",
    "        \n",
    "        return result\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        if not head:\n",
    "            return True\n",
    "\n",
    "        mid = self.mid_node(head)\n",
    "        post = self.reverse(mid.next)\n",
    "\n",
    "        p1 = head\n",
    "        p2 = post\n",
    "        while p2:\n",
    "            if p1.val != p2.val:\n",
    "                return False\n",
    "            p1 = p1.next\n",
    "            p2 = p2.next\n",
    "\n",
    "        return True\n",
    "        \n",
    "\n",
    "    def mid_node(self, head):\n",
    "        fast = head\n",
    "        slow = head\n",
    "        while fast.next and fast.next.next:\n",
    "            fast = fast.next.next\n",
    "            slow = slow.next\n",
    "\n",
    "        return slow\n",
    "\n",
    "    def reverse(self, head):\n",
    "        pre = None\n",
    "        cur = head\n",
    "        while cur:\n",
    "            next_node = cur.next\n",
    "            cur.next = pre\n",
    "            pre = cur\n",
    "            cur = next_node\n",
    "\n",
    "        return pre\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        slow, fast = head, head\n",
    "        while fast and fast.next:\n",
    "            slow = slow.next\n",
    "            fast = fast.next.next\n",
    "        if fast:\n",
    "            slow = slow.next\n",
    "\n",
    "        tail = None\n",
    "        while slow:\n",
    "            nxt = slow.next\n",
    "            slow.next = tail\n",
    "            tail, slow = slow, nxt\n",
    "        \n",
    "        while tail:\n",
    "            if tail.val != head.val:\n",
    "                return False\n",
    "            head = head.next\n",
    "            tail = tail.next\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        nums=[]\n",
    "        while head:\n",
    "            nums.append(head.val)\n",
    "            head=head.next\n",
    "        \n",
    "        temp=nums.copy()\n",
    "        temp.reverse()\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i]!=temp[i]:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        ptr = head\n",
    "        vals =[]\n",
    "        while ptr is not None:\n",
    "            vals.append(ptr.val)\n",
    "            ptr = ptr.next\n",
    "        return vals ==vals[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        val = []\n",
    "        pointer = head\n",
    "        while pointer:\n",
    "            val.append(pointer.val)\n",
    "            pointer = pointer.next\n",
    "\n",
    "        return val == val[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        cur=head\n",
    "        s=\"\"\n",
    "        while cur:\n",
    "           s+=str(cur.val)\n",
    "           cur=cur.next\n",
    "        return s==s[::-1] "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        if (not head) or (not head.next):\n",
    "            return True\n",
    "        slow_p, fast_p = ListNode(next=head), ListNode(next=head)\n",
    "        pre_harsh, F_JI = {}, True\n",
    "        while fast_p:\n",
    "            pre_harsh[slow_p.next] = slow_p\n",
    "            if not fast_p.next:\n",
    "                F_JI = False   # 长度为偶数\n",
    "                break\n",
    "            slow_p = slow_p.next\n",
    "            fast_p = fast_p.next.next\n",
    "        if F_JI:\n",
    "            back_p = pre_harsh[slow_p]\n",
    "        else:\n",
    "            back_p = slow_p\n",
    "        slow_p = slow_p.next\n",
    "        while slow_p:\n",
    "            if slow_p.val != back_p.val:\n",
    "                return False\n",
    "            slow_p = slow_p.next\n",
    "            back_p = pre_harsh[back_p]\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        A = head\n",
    "        d = {}\n",
    "        i = 0\n",
    "        while A:\n",
    "            d[i] = A\n",
    "            A = A.next\n",
    "            i += 1\n",
    "        L, R = 0, i-1\n",
    "        while L < R:\n",
    "            if d[L].val != d[R].val:\n",
    "                return False\n",
    "            L += 1\n",
    "            R -= 1\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        a=head\n",
    "        vl={}\n",
    "        b=0\n",
    "        while a!=None:\n",
    "            vl[b]=a.val\n",
    "            b+=1\n",
    "            a=a.next\n",
    "        b-=1\n",
    "        for i in range(b//2+1):\n",
    "            if vl[i] != vl[b-i]:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        dummy = ListNode(0, head)\n",
    "        p, q = dummy, dummy\n",
    "        while q and q.next:\n",
    "            p = p.next\n",
    "            q = q.next.next\n",
    "        l, r = head, self.reverseList(p.next)\n",
    "        while l and r:\n",
    "            if l.val != r.val:\n",
    "                return False\n",
    "            l = l.next\n",
    "            r = r.next\n",
    "        return True\n",
    "\n",
    "    \n",
    "    def reverseList(self, head):\n",
    "        if not head or not head.next:\n",
    "            return head\n",
    "        \n",
    "        cur = self.reverseList(head.next)\n",
    "        head.next.next = head\n",
    "        head.next = None\n",
    "        return cur\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        slow, fast =  head, head\n",
    "\n",
    "        while fast.next and fast.next.next:\n",
    "            slow = slow.next\n",
    "            fast = fast.next.next\n",
    "\n",
    "        right = self.reverse(slow.next)\n",
    "        left = head\n",
    "\n",
    "        while right:\n",
    "            if left.val != right.val:\n",
    "                return False\n",
    "            left = left.next\n",
    "            right = right.next\n",
    "\n",
    "        return True\n",
    "\n",
    "    def reverse(self, head):\n",
    "        if not head or not head.next:\n",
    "            return head\n",
    "\n",
    "        cur = self.reverse(head.next)\n",
    "        head.next.next = head\n",
    "        head.next = None\n",
    "        return cur"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def _base(self, left, right):\n",
    "        if right.next is None:\n",
    "            return True, left.next\n",
    "        if right.next.next is None:\n",
    "            return left.val == left.next.val, left.next.next\n",
    "        ret, node = self._base(left.next, right.next.next)\n",
    "        if ret is False:\n",
    "            return False, None\n",
    "        return left.val == node.val, node.next\n",
    "\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        if not head:\n",
    "            return False\n",
    "\n",
    "        if head and head.next is None:\n",
    "            return True\n",
    "\n",
    "        left = right = head\n",
    "        # 递归调用\n",
    "        ret, node = self._base(left, right)\n",
    "        return ret\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        if not head or not head.next:\n",
    "            return True\n",
    "        fast = slow = head\n",
    "        while fast and fast.next:\n",
    "            fast = fast.next.next\n",
    "            slow = slow.next\n",
    "        def reverseList(head):\n",
    "            if not head or not head.next:\n",
    "                return head\n",
    "            newH = reverseList(head.next)\n",
    "            head.next.next = head\n",
    "            head.next = None\n",
    "            return newH\n",
    "        newH = reverseList(slow)\n",
    "        while newH:\n",
    "            if head.val != newH.val:\n",
    "                return False\n",
    "            newH = newH.next\n",
    "            if newH is None:\n",
    "                break\n",
    "            head = head.next\n",
    "        return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        \n",
    "        def reverseLinkList(root):\n",
    "            if not root.next:\n",
    "                return root\n",
    "            node = reverseLinkList(root.next)\n",
    "            node.next = root\n",
    "            return root\n",
    "\n",
    "        s, f = head, head.next\n",
    "        while f and f.next:\n",
    "            f = f.next.next if f.next.next else f.next\n",
    "            s = s.next\n",
    "        \n",
    "        reverseLinkList(s)\n",
    "        s.next = None\n",
    "\n",
    "        left, right = head, f\n",
    "        while left and right:\n",
    "            if left.val != right.val:\n",
    "               return False\n",
    "            left, right = left.next, right.next\n",
    "\n",
    "        return True\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        fake_head = ListNode(0)\n",
    "        fake_head.next = head\n",
    "        fast = fake_head\n",
    "        slow = fake_head\n",
    "        while fast and fast.next and fast.next.next:\n",
    "            fast = fast.next.next\n",
    "            slow = slow.next\n",
    "        start = slow.next\n",
    "        slow.next = None\n",
    "        if fast.next:\n",
    "            tmp = start.next\n",
    "            start.next = None\n",
    "            start = tmp\n",
    "        def backup(node):\n",
    "            if not node or not node.next:\n",
    "                return node\n",
    "            ans = backup(node.next)\n",
    "            node.next.next = node\n",
    "            node.next = None\n",
    "            return ans\n",
    "        newHead = backup(start)\n",
    "        while head and newHead:\n",
    "            if head.val != newHead.val:\n",
    "                return False\n",
    "            head = head.next\n",
    "            newHead = newHead.next\n",
    "        return True if not head and not newHead else False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "\n",
    "\n",
    "        def reverse_node(node):\n",
    "            if not node:\n",
    "                return\n",
    "            next_node = reverse_node(node.next)\n",
    "            if next_node is None:\n",
    "                return node\n",
    "            node.next.next = node\n",
    "            node.next = None\n",
    "            return next_node\n",
    "        slow =fast =head\n",
    "        while fast.next:\n",
    "            slow = slow.next\n",
    "            fast = fast.next\n",
    "            if not fast.next:\n",
    "                break\n",
    "            fast = fast.next\n",
    "        cmp_node= reverse_node(slow)\n",
    "        # print(cmp_node)\n",
    "        while  cmp_node:\n",
    "            if cmp_node.val !=head.val:\n",
    "                return False\n",
    "            cmp_node = cmp_node.next\n",
    "            head = head.next\n",
    "        # if head or cmp_node:\n",
    "        #     return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        # # 后序遍历\n",
    "        # global left\n",
    "        # left = head\n",
    "        # return self.traverse(head)\n",
    "\n",
    "        # 快慢指针法\n",
    "        slow, fast = head, head\n",
    "        while fast and fast.next:\n",
    "            fast = fast.next.next\n",
    "            slow = slow.next\n",
    "        if fast:\n",
    "            slow = slow.next\n",
    "\n",
    "        left, right = head, self.reverse(slow)\n",
    "        while left and right:\n",
    "            if left.val != right.val:\n",
    "                return False\n",
    "            left = left.next\n",
    "            right = right.next\n",
    "        return True\n",
    "\n",
    "    def reverse(self, head):\n",
    "        if not head or not head.next:\n",
    "            return head\n",
    "        cur = self.reverse(head.next)\n",
    "        head.next.next = head\n",
    "        head.next = None\n",
    "        return cur\n",
    "\n",
    "    def traverse(self, head):\n",
    "        global left\n",
    "        if not head:\n",
    "            return True\n",
    "\n",
    "        res = self.traverse(head.next)\n",
    "        res = res and (left.val == head.val)\n",
    "        left = left.next\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        if head.next == None:\n",
    "            return True\n",
    "        else:\n",
    "            # 找到中心结点\n",
    "            slow = head\n",
    "            fast = head\n",
    "            while fast.next:\n",
    "                fast = fast.next\n",
    "                if fast.next:\n",
    "                    fast = fast.next\n",
    "                    slow = slow.next\n",
    "                else:\n",
    "                    break\n",
    "            # 递归反转链表\n",
    "            def recur(head):\n",
    "                if not head.next:\n",
    "                    return head, head\n",
    "                else:\n",
    "                    head_, tail_ = recur(head.next)\n",
    "                    tail_.next = head\n",
    "                    return head_, head\n",
    "            \n",
    "            # 反转slow之后的链表\n",
    "            half_head, half_tail = recur(slow.next)\n",
    "            half_tail.next = None\n",
    "            slow.next = None\n",
    "            # 对比\n",
    "            while half_head:\n",
    "                if half_head.val != head.val:\n",
    "                    return False    \n",
    "                half_head = half_head.next\n",
    "                head = head.next\n",
    "\n",
    "            return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        i = 0\n",
    "        a = head\n",
    "        while a is not None:\n",
    "            i += 1\n",
    "            a = a.next\n",
    "\n",
    "        if i & 1 == 0:\n",
    "            i //= 2\n",
    "        else:\n",
    "            i = (i // 2) + 1\n",
    "\n",
    "        a = head\n",
    "        while i > 1:\n",
    "            a = a.next\n",
    "            i -= 1\n",
    "\n",
    "        def rev(prev, node):\n",
    "            if node is None:\n",
    "                return prev\n",
    "            tmp = node.next\n",
    "            node.next = prev\n",
    "            return rev(node, tmp)\n",
    "\n",
    "        a.next = rev(None, a.next)\n",
    "        a = a.next\n",
    "        while a is not None:\n",
    "            if head.val != a.val:\n",
    "                return False\n",
    "            head = head.next\n",
    "            a = a.next\n",
    "\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        \"\"\"\n",
    "        判断是否为回文链表\n",
    "        转化为数组，再用递归做回文判断\n",
    "        要素一：函数的功能是数组是否为回文\n",
    "        要素二：终止条件是空素数组或只含一个元素的数组\n",
    "        要素三：拆分公式是当前数组首尾元素相等&&除首尾结点外的数组是否为回文\n",
    "        head = [1,2,3,3,2,1]\n",
    "        \"\"\"\n",
    "        res = []\n",
    "        while head:\n",
    "            res.append(head.val)\n",
    "            head = head.next \n",
    "        def arrIsPalindrome(arr, start, end):\n",
    "            if start >= end:\n",
    "                return True\n",
    "            return arr[start]==arr[end] and arrIsPalindrome(arr, start+1, end-1)\n",
    "        return arrIsPalindrome(res, 0, len(res)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        if not head or not head.next:\n",
    "            return True\n",
    "\n",
    "        self.cur = head\n",
    "        self.count = 0\n",
    "        self.cur_count = 0\n",
    "\n",
    "        return self.trave(head)\n",
    "        \n",
    "\n",
    "    def trave(self, node):\n",
    "        if not node:\n",
    "            return True\n",
    "\n",
    "        self.count += 1\n",
    "        if not self.trave(node.next):\n",
    "            return False\n",
    "        \n",
    "        if self.cur_count >= self.count // 2:\n",
    "            return True\n",
    "        \n",
    "        if self.cur.val != node.val:\n",
    "            return False\n",
    "\n",
    "        self.cur_count += 1\n",
    "        self.cur = self.cur.next\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def somehow(self, head: ListNode, cur: ListNode, res: dict) -> ListNode:\n",
    "        if cur is None:\n",
    "            return head\n",
    "        ret = self.somehow(head, cur.next, res)\n",
    "        \n",
    "        if cur.val != ret.val:\n",
    "            res[\"res\"] = False\n",
    "        \n",
    "        return ret.next\n",
    "\n",
    "    \n",
    "\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "\n",
    "        res = {\"res\": True}\n",
    "   \n",
    "        self.somehow(head, head, res)\n",
    "\n",
    "        return res[\"res\"]\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "\n",
    "        self.front_pointer = head\n",
    "\n",
    "        def recursively_check(current_node=head):\n",
    "            if current_node is not None:\n",
    "                if not recursively_check(current_node.next):\n",
    "                    return False\n",
    "                if self.front_pointer.val != current_node.val:\n",
    "                    return False\n",
    "                self.front_pointer = self.front_pointer.next\n",
    "            return True\n",
    "\n",
    "        return recursively_check()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        self.frontNode = head\n",
    "        def recursion(currentNode=head):\n",
    "            if currentNode is not None:\n",
    "                if not recursion(currentNode.next):\n",
    "                    return False\n",
    "                if self.frontNode.val != currentNode.val:\n",
    "                    return False\n",
    "                self.frontNode = self.frontNode.next\n",
    "            return True\n",
    "        return recursion(head)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        self.front_point = head\n",
    "\n",
    "        def checkRecur(curNode):\n",
    "            if curNode is None :\n",
    "                return True\n",
    "            if not checkRecur(curNode.next):\n",
    "                return False\n",
    "            if self.front_point.val !=curNode.val:\n",
    "                return False\n",
    "            self.front_point = self.front_point.next\n",
    "            return True\n",
    "        return checkRecur(head)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
